#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int numTrees(int n);

int main()
{
	return 0;
}

int numTrees(int n)
{
	int* G = calloc(n + 1, sizeof(int));
	G[0] = G[1] = 1;
	for (int i = 2; i <= n; i++)
		for (int j = 1; j <= i; j++)
			G[i] += G[j - 1] * G[i - j];
	int res = G[n];
	free(G);
	return res;
}
